09. CODE: Add New Neighbors

Add New Neighbors

Before you will be able to finish writing the AStarSearch method, you will need a way to add new nodes to the search.In this exercise, you will will write a RoutePlanner::AddNeighbors method for this purpose.

This method will take each neighbor of the current node in the A* search, set the neighbor's g-value, h-value, and parent, and add the neighbor to the open list. To do this, you will use the RouteModel::Node::FindNeighbors(), and the CalculateHValue method that you have written previously.

## To complete this exercise:

  1. Modify route_planner.h to include a private method declaration for the AddNeighbors method. This method should accept a pointer to a RouteModel::Node object as the argument, and since the method is just modifying the RoutePlanner instance variable open_list, the method can have void return type.
  2. In route_planner.cpp define the AddNeighbors method using the FindNeighbors and CalculateHValue methods. Use the pseudocode below as a guideline:

## Pseudocode:

AddNeighbors(RouteModel::Node *current_node):

  1. Call FindNeighbors() on current_node to populate the current_node's neighbors vector.
  2. For each neighbor in the current_node's neighbors
  1. Set the neighbors parent to the current_node.
    1. Set the neighbor's g_value to the sum of the current_node's g_value plus the distance from the curent_node to the neighbor.
    2. Set the neighbor's h_value using CalculateHValue
    3. Push the neighbor to the back of the open_list.
    4. Mark the neighbor as visited.

Note: This exercise does not have any tests associated with it, but you will be completing A* search in the next exercise, and the code will be tested with the results of AStarSearch().

Workspace

This section contains either a workspace (it can be a Jupyter Notebook workspace or an online code editor work space, etc.) and it cannot be automatically downloaded to be generated here. Please access the classroom with your account and manually download the workspace to your local machine. Note that for some courses, Udacity upload the workspace files onto https://github.com/udacity, so you may be able to download them there.

Workspace Information:

  • Default file path:
  • Workspace type: react
  • Opened files (when workspace is loaded): n/a
  • userCode:

    export CXX=g++-7
    export CXXFLAGS=-std=c++17
    cmake_tests() {
    /usr/local/bin/cmake -DTESTING="AStarStub" "$1"
    }
    export -f cmake_tests

Solution

Add Neighbors

Next Concept